Search for: All records

We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd\H{o}s-R\'enyi , which has independent edges, we take the ambient graph to be the \emph{random graph with triangles} (RGT) obtained by adding triangles to . We show that the RGT can be efficiently mapped to the corresponding , and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd\H{o}s-R\'enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on \emph{low sensitivity to perturbations}. 

We aim to understand the extent to which the noise distribution in a planted signal-plusnoise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd˝os-R´enyi G(n, p), which has independent edges, we take the ambient graph to be the random graph with triangles (RGT) obtained by adding triangles to G(n, p). We show that the RGT can be efficiently mapped to the corresponding G(n, p), and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd˝os-R´enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations.